package everydayGrade.t1;

import org.junit.jupiter.api.Test;

import java.util.ArrayList;
import java.util.List;

/**
 * @Author: Siantar
 * @Date: 2023-11-13-20:48
 * @Description: 1.0
 */
public class T0699 {
    public List<Integer> fallingSquares(int[][] positions) {
        List<Integer> res = new ArrayList<>();
        for (int[] position : positions) {
            int l = position[0], a = position[1];
            int r = l + a - 1;
            int mh = query(root, 0, N, l, r);
            update(root, 0, N, l, r, mh + a);
            res.add(query(root, 0, N, 0, N));
        }
        return res;
    }

    class Node {
        Node left, right;
        int value, change;
    }

    public Node root = new Node();
    public int N = (int) 1e9;

    public void update(Node node, int start, int end, int left, int right, int change) {
        if (left <= start && end <= right) {
            node.value = change;
            node.change = change;
            return;
        }
        int mid = start + ((end - start) >> 1);
        pushDown(node, mid - start + 1, end - mid);
        if (left <= mid) update(node.left, start, mid, left, right, change);
        if (mid < right) update(node.right, mid + 1, end, left, right, change);
        pushUp(node);
    }

    public int query(Node node, int start, int end, int left, int right) {
        if (left <= start && end <= right) {
            return node.value;
        }
        int mid = start + ((end - start) >> 1), ans = 0;
        pushDown(node, mid - start + 1, end - mid);
        if (left <= mid) ans = Math.max(ans, query(node.left, start, mid, left, right));
        if (mid < right) ans = Math.max(ans, query(node.right, mid + 1, end, left, right));
        return ans;
    }


    public void pushUp(Node node) {
        node.value = Math.max(node.left.value, node.right.value);
    }

    public void pushDown(Node node, int leftNum, int rightNum) {
        if (node.left == null) node.left = new Node();
        if (node.right == null) node.right = new Node();
        if (node.change == 0) return;
        node.left.value = node.change;
        node.right.value = node.change;
        node.left.change = node.change;
        node.right.change = node.change;
        node.change = 0;
    }
    @Test
    public void test() {
        update(root,0,N,6,9,4);
        System.out.println(query(root,0,N,2,8));
        update(root,0,N,2,8,11);
        System.out.println(query(root,0,N,6,14));
        update(root,0,N,6,14,20);
        System.out.println(query(root,0,N,0,N));
    }
}
